// 带头结点的链表
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define ERROR -999

typedef int ElementType;
struct Node
{
    ElementType Data;
    struct Node* Next;
};
typedef struct Node* PtrToNode;
typedef PtrToNode List;

List CreateList()
{
    PtrToNode head = (PtrToNode) malloc(sizeof(struct Node));
    head->Next = NULL;
    return head;
}

bool Insert_r(List L, ElementType X)
{
    PtrToNode TmpNode = (PtrToNode) malloc(sizeof(struct Node));
    TmpNode->Data = X;
    TmpNode->Next = NULL;

    PtrToNode p = L;
    while (p->Next != NULL) {
        p = p->Next;
    }
    p->Next = TmpNode;
    return true;
}

bool Insert_f(List L, ElementType X)
{
    PtrToNode TmpNode = (PtrToNode) malloc(sizeof(struct Node));
    TmpNode->Data = X;
    TmpNode->Next = L->Next;
    L->Next = TmpNode;
    return true;
}

ElementType Delete(List L, ElementType X)
{
    PtrToNode p = L;
    PtrToNode q = NULL;
    ElementType resultVal;
    while (p->Next != NULL) {
        if (p->Next->Data == X) {
            q = p->Next;
            resultVal = q->Data;
            p->Next = p->Next->Next;
            free(q);
            return resultVal;
        }
        p = p->Next;
    }
    return ERROR;
}

void Print_List(List L)
{
    PtrToNode p = L;
    while (p->Next != NULL) {
        p = p->Next;
        printf("%d ", p->Data);
    }
}

int main()
{
    List L = CreateList();
    Insert_r(L, 1);
    Insert_r(L, 2);
    Insert_r(L, 3);
    Insert_r(L, 4);
    Insert_r(L, 5);
    // Insert_f(L, 1);
    // Insert_f(L, 2);
    // Insert_f(L, 3);
    // Insert_f(L, 4);
    // Insert_f(L, 5);
    Delete(L, 29);
    Print_List(L);
}